//根据一棵树的前序序列(标明遍历时为空的树为#),构建出这棵树,再对这棵树进行三种遍历
#include <stdio.h>
#include <stdlib.h>
typedef struct treenode
{
    char data;
    struct treenode *left;
    struct treenode *right;
} *Tree, TreeNode;
char s[100];
int i;
Tree origin_tree(Tree &T)
{
    if (s[i++] == '#')
    {
        return NULL;
    }
    T = (Tree)malloc(sizeof(TreeNode));
    T->data = s[i - 1];
    T->left = origin_tree(T->left);
    T->right = origin_tree(T->right);
    return T;
}
void preOrder(Tree T)
{
    if (T == NULL)
    {
        return;
    }
    printf("%c", T->data);
    preOrder(T->left);
    preOrder(T->right);
}
void inOrder(Tree T)
{
    if (T == NULL)
    {
        return;
    }
    inOrder(T->left);
    printf("%c", T->data);
    inOrder(T->right);
}
void postOrder(Tree T)
{
    if (T == NULL)
    {
        return;
    }
    postOrder(T->left);
    postOrder(T->right);
    printf("%c", T->data);
}
void freetree(Tree &T)
{
    if (T == NULL)
    {
        return;
    }
    freetree(T->left);
    freetree(T->right);
    free(T);
}
int main()
{
    scanf("%s", s);
    Tree T;
    origin_tree(T);
    preOrder(T);
    printf("\n");
    inOrder(T);
    printf("\n");
    postOrder(T);
    freetree(T);
}
/*
输入ABD##EG###C#F##
输出ABDEGCF
   DBGEACF
   DGEBFCA

*/